{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "04d57ea5-7a1d-4c7f-8aaf-4f0c6bbc8a35",
   "metadata": {},
   "source": [
    "# Quantum Arithmetic Circuits\n",
    "\n",
    "<a href=\"https://gitee.com/mindspore/docs/blob/master/docs/mindquantum/docs/source_en/quantum_arithmetic_circuit.ipynb\" target=\"_blank\"><img src=\"https://mindspore-website.obs.cn-north-4.myhuaweicloud.com/website-images/master/resource/_static/logo_source_en.png\"></a>\n",
    "\n",
    "## Summary\n",
    "\n",
    "This tutorial includes the implementation of 4-bit VBE quantum adder, subtractor, modular adder, modular multiplier and modular exponentiation circuit with Mindquantum. There is a progressive relationship between them, i.e., modular adder is based on adder, modular multiplier is based on modular adder and modular exponentiation circuit is based on multiplier multipliers.\n",
    "\n",
    "The function of arithmetic circuits can be summarised as follow:\n",
    "\n",
    "* adder, giving output: $a+b$;\n",
    "* subtractor, output: $b-a$;\n",
    "* modular adder, output: $(a + b) mod N$;\n",
    "* modular mulplier, output: $a x mod N$;\n",
    "* modular exponentiation circuit, output: $a^x mod N$.\n",
    "\n",
    "while $a, b, x, N$ are some non-negtive integrals.\n",
    "\n",
    "## Introduction\n",
    "\n",
    "The development of quantum computing field has is now on the rise due to the technology advances and the computational advantages of some quantum algorithms over their classical counterpart. One of the most influential quantum algorithms is Shor's algorithm for integer factorization problem which offers super-polynomial speedup, threating the security of widely-used RSA cryptosystems when large number of qubits exist in the future. The critical circuit of Shor's algorithm is modular exponentiation circuit. Vedral, Barenco and Ekert (VBE) proposed earliest how to build quantum arithmetic circuits, including the modular exponentiation circuit, here we give the implementations of them.\n",
    "\n",
    "This tutorial is mainly the implementation of paper: [H. T. Larasati and H. Kim, \"Simulation of Modular Exponentiation Circuit for Shor's Algorithm in Qiskit, 2020](https://ieeexplore.ieee.org/document/9310794).\n",
    "\n",
    "## Arithmetic Circuits\n",
    "\n",
    "### Adder & Subtrator\n",
    "\n",
    "The figure numbers in this tutorial coincides with original paper to help reader refer to them. VBE adder which maps quantum state $|a, b\\rangle \\rightarrow |a, a+b\\rangle$ is shown in `Fig.1` . Three registers are required: Register A and B, each to contain the input a and b, respectively, and a carry register to hold the carry value during computation. The sum is store at register S($s_3 s_2 s_1 s_0$). $3n+1$ qubits is required for the for a n-bit adder. The CARRY, SUM and Reverse CARRY blocks in figure convert the binary logic to controlled gates in quantum circuit. Their functions are calculating carry, sum and uncompute carry. e.g., for the first vertical line in the first CARRY block，the carry bit(forth line) is $1$ only when $a_0, b_0$ are both $1$.\n",
    "\n",
    "<img src=\"images/Fig1_3bit_adder.jpg\" width=600>\n",
    "\n",
    "The implementation of 4-bit adder circuit is shown in `Fig.6` . When applied backwards, this circuit performs the subtraction $|a, b\\rangle \\rightarrow |a, b-a\\rangle$. When $b < a$ , meaning that\n",
    "subtraction will yield negative number, the circuit will output the result in two’s complements form: the n+1 bit will be in state $|1\\rangle$ in this case. This reversed circuit, which is also the inverse for this case, is often referred to as *subtractor*, *reversed adder*, or $adder^{-1}$. A implementation of subtractor is drawn in `Fig.7` .\n",
    "\n",
    "<img src=\"images/Fig6_adder.jpg\" width=600>\n",
    "\n",
    "<img src=\"images/Fig7_subtractor.jpg\" width=600>\n",
    "\n",
    "Here we show the code of adder( `Fig.6` ) and subtractor( `Fig.7` ) with Mindquantum.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8c15251b-44d1-4168-86f4-02a5593b7fed",
   "metadata": {},
   "outputs": [],
   "source": [
    "from mindquantum.core.gates import X, SWAP\n",
    "from mindquantum.core.circuit import Circuit, shift, UN"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "a7771058-a7f8-474a-bf9d-cf5f30797ee3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def Adder() -> Circuit:\n",
    "    \"\"\"4-bit adder, from Fig.6\n",
    "    \"\"\"\n",
    "    return Circuit([\n",
    "        X(10, [4, 0]),\n",
    "        X(11, [5, 1]),\n",
    "        X(12, [6, 2]),\n",
    "        X(8, [7, 3]),\n",
    "        X(4, 0),\n",
    "        X(5, 1),\n",
    "        X(6, 2),\n",
    "        X(7, 3),\n",
    "        X(10, [9, 4]),\n",
    "        X(11, [10, 5]),\n",
    "        X(12, [11, 6]),\n",
    "        X(8, [7, 12]),\n",
    "        X(7, 12),\n",
    "        X(12, [11, 6]),\n",
    "        X(6, 2),\n",
    "        X(12, [6, 2]),\n",
    "        X(6, 2),\n",
    "        X(6, 11),\n",
    "        X(11, [10, 5]),\n",
    "        X(5, 1),\n",
    "        X(11, [5, 1]),\n",
    "        X(5, 1),\n",
    "        X(5, 10),\n",
    "        X(10, [9, 4]),\n",
    "        X(4, 0),\n",
    "        X(10, [4, 0]),\n",
    "        X(4, 0),\n",
    "        X(4, 9)\n",
    "    ])\n",
    "\n",
    "\n",
    "def AdderRev() -> Circuit:\n",
    "    \"\"\"4-bit reversed adder (subtractor), from Fig.7\n",
    "    \"\"\"\n",
    "    return Circuit([\n",
    "        X(4, 9),\n",
    "        X(4, 0),\n",
    "        X(10, [4, 0]),\n",
    "        X(4, 0),\n",
    "        X(10, [9, 4]),\n",
    "        X(5, 10),\n",
    "        X(5, 1),\n",
    "        X(11, [5, 1]),\n",
    "        X(5, 1),\n",
    "        X(11, [10, 5]),\n",
    "        X(6, 11),\n",
    "        X(6, 2),\n",
    "        X(12, [6, 2]),\n",
    "        X(6, 2),\n",
    "        X(12, [11, 6]),\n",
    "        X(7, 12),\n",
    "        X(8, [7, 12]),\n",
    "        X(7, 3),\n",
    "        X(12, [6, 2]),\n",
    "        X(8, [7, 3]),\n",
    "        X(6, 2),\n",
    "        X(12, [11, 6]),\n",
    "        X(11, [5, 1]),\n",
    "        X(5, 1),\n",
    "        X(11, [10, 5]),\n",
    "        X(10, [4, 0]),\n",
    "        X(4, 0),\n",
    "        X(10, [9, 4])\n",
    "    ])"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "edcf41e3-8223-40fe-9e47-381a6a693f81",
   "metadata": {},
   "source": [
    "Invresed adder(subtractor) can be obtained easily from with method `reverse()` . e.g.:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "ca21247b-ee5f-47ae-b990-f98ddb910c95",
   "metadata": {},
   "outputs": [],
   "source": [
    "def AdderRev2() -> Circuit:\n",
    "    \"\"\"Reversed-adder\"\"\"\n",
    "    cir = Adder()\n",
    "    cir.reverse()\n",
    "    return cir"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "baf7effe-8549-4d77-87f9-7681e27c9e3c",
   "metadata": {},
   "source": [
    "For convenience, here we give two functions: `c2q(...)` and `q2c(...)` , which convert the intergal to quantum circuit and measure quantum circuit to get a integral respectively.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "c390dd43-e4f1-4cbb-9d1e-d55996aaaa23",
   "metadata": {},
   "outputs": [],
   "source": [
    "def c2q(qlist: list, value: int) -> Circuit:\n",
    "    \"\"\"Convert integral `value` to specific bit of a quantum circuit.\n",
    "    Args:\n",
    "        qlist:  list[int]: Specific qubit to store the integral with smaller\n",
    "                           digit at the end, such as [3,2,1,0].\n",
    "        value:  int:       The non-negtive decimal integral.\n",
    "    Return:\n",
    "        Prepared circuit.\n",
    "    \"\"\"\n",
    "    vbin = bin(value)[2:][::-1]\n",
    "    qlist = qlist[::-1]\n",
    "    cir = Circuit([X.on(q) for q, v in zip(qlist, vbin) if v == '1'])\n",
    "    return cir\n",
    "\n",
    "\n",
    "def q2c(cir: Circuit, qlist: list) -> int:\n",
    "    \"\"\"Measure the circuit to get the circuit state.\n",
    "    Args:\n",
    "        cir:   Quantum circuit.\n",
    "        qlist: The bit list need to be measured, e.g. the [q2, q1, q0] is\n",
    "               means int(q2q1q0).\n",
    "    Return:\n",
    "        The measure value in decimal way.\n",
    "    \"\"\"\n",
    "    ket_str = cir.get_qs(ket=True)\n",
    "    print(f'ket string: {ket_str}')\n",
    "    res_str = \"\"\n",
    "    for q in qlist:\n",
    "        res_str += ket_str[-q-2]\n",
    "    return int(res_str, base=2)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "9b80cc48-1920-42b5-8ebc-2abb391f14e0",
   "metadata": {},
   "source": [
    "Now we verify the *adder* and *subtractor* with $a=3, b=8, a+b=11, b-a=5$. Here is the code.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "6c99fda9-d153-4b53-bd73-11a82aa25b9e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Verify adder & subtractor:\n",
      "ket string: 1¦0000010110011⟩\n",
      "ket string: 1¦0010001010011⟩\n",
      "q_add = 11, c_add = 11\n",
      "q_sub = 5, c_sub = 5\n",
      "\n"
     ]
    }
   ],
   "source": [
    "def demo1():\n",
    "    \"\"\"Verify Fig.6 (adder), Fig.7 (subtractor)\n",
    "    \"\"\"\n",
    "    print(\"Verify adder & subtractor:\")\n",
    "    # verify b + a, b - a\n",
    "    a = 3\n",
    "    b = 8\n",
    "    # Assign `a` to the 3,2,1,0 circuit.\n",
    "    cir_a = c2q([3, 2, 1, 0], a)\n",
    "    cir_b = c2q([7, 6, 5, 4], b)\n",
    "\n",
    "    cir_add = cir_a + cir_b + Adder()\n",
    "    # Measure the quantum circuit to get the result.\n",
    "    q_add = q2c(cir_add, [7, 6, 5, 4])\n",
    "\n",
    "    cir_sub = cir_a + cir_b + AdderRev()\n",
    "    q_sub = q2c(cir_sub, [7, 6, 5, 4])\n",
    "\n",
    "    print(\n",
    "        f\"q_add = {q_add}, c_add = {b + a}\\nq_sub = {q_sub}, c_sub = {b - a}\\n\")\n",
    "\n",
    "\n",
    "demo1()"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "f19c0df8-8414-4ad9-a326-68a3f329ebf5",
   "metadata": {},
   "source": [
    "Where the `q_` at the beginning means `quantum` result, `c_` means classical (correct) value, `add` and `sub` mean adder and subtractor respectively, `ket string` is the final state of circuit. The circuit gains the correct answer for giving value.\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "476ea679-1fab-4a70-b977-e24de570dc5c",
   "metadata": {},
   "source": [
    "### Modular Adder\n",
    "\n",
    "Modular adder maps $|a, b\\rangle \\rightarrow |a, (a+b) mod N\\rangle$. VBE modular adder makes use of the concept of two’s complements to detect the comparison. As shown in Fig. 2, it uses 5 adders (3 adders and 2 reversed adder to be specific, but we refer them generally as adders for this case), in which the first two are for performing $a+b-N$, the third is for adding back if the former operation yield negative values (indicated by the values stored in the Temp Qubit, which is controlled by the MSB of Register B, $b_{n+1}$), and another two are for restoring the temp qubit bit back to $|0\\rangle$. As with the adder, the computation result is stored in Register B.\n",
    "\n",
    "<img src=\"images/Fig2_modular_adder.jpg\" width=600>\n",
    "\n",
    "`Fig.8` presents the implementation of a 4-bit modular adder, in which gray lines at the first and last part of the circuit is used to separate the inputs with the “internal” part of the circuit.\n",
    "\n",
    "<img src=\"images/Fig8_modular_adder.jpg\" width=600>\n",
    "\n",
    "The code of Modular adder and verification are as following.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "32884490-89cd-4cd5-b530-e4214ae8ffdb",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Verify modular adder:\n",
      "ket string: 1¦000000000001011011⟩\n",
      "q_add = 5, c_add = 5\n"
     ]
    }
   ],
   "source": [
    "def ModAdder() -> Circuit:\n",
    "    \"\"\"Modular adder, from Fig.8\n",
    "    \"\"\"\n",
    "    cir = Circuit()\n",
    "    cir += Adder()\n",
    "    cir += UN(SWAP, maps_obj=[(0, 13), (1, 14), (2, 15), (3, 16)])\n",
    "    cir += AdderRev2()\n",
    "    cir += Circuit([X(8), X(17, 8), X(8)])\n",
    "    cir += UN(X, maps_obj=[0, 1, 2, 3], maps_ctrl=[17, 17, 17, 17])\n",
    "    cir += Adder()\n",
    "    cir += UN(X, maps_obj=[0, 1, 2, 3], maps_ctrl=[17, 17, 17, 17])\n",
    "    cir += UN(SWAP, maps_obj=[(0, 13), (1, 14), (2, 15), (3, 16)])\n",
    "    cir += AdderRev2()\n",
    "    cir += X(17, 8)\n",
    "    cir += Adder()\n",
    "    return cir\n",
    "\n",
    "\n",
    "def demo2():\n",
    "    \"\"\"Verify modular adder\n",
    "    \"\"\"\n",
    "    print(\"Verify modular adder:\")\n",
    "    # 1. Get (a + b) mod n\n",
    "    # 2. Get (b - a) mod n\n",
    "    a = 11\n",
    "    b = 9\n",
    "    n = 15\n",
    "    # encoding the decimals\n",
    "    cir_a = c2q([3, 2, 1, 0], a)\n",
    "    cir_b = c2q([7, 6, 5, 4], b)\n",
    "    cir_n = c2q([16, 15, 14, 13], n)\n",
    "    # full adder circuit\n",
    "    cir_madd = cir_a + cir_b + cir_n + ModAdder() + cir_n\n",
    "    # measure to get the result\n",
    "    q_add = q2c(cir_madd, [7, 6, 5, 4])\n",
    "    # correct value\n",
    "    c_add = (a + b) % n\n",
    "    print(f\"q_add = {q_add}, c_add = {c_add}\")\n",
    "\n",
    "\n",
    "demo2()"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "eea29e0d-cc94-48f9-ab8c-8af6f6ed5a6c",
   "metadata": {},
   "source": [
    "### Modular Multiplier\n",
    "\n",
    "Modular multiplier maps $|x, 0\\rangle \\rightarrow |x, ax mod N\\rangle$. There is a control bit ($control_0$ or $|c\\rangle$), if $control_0 = 0$，then the maps is $|x, 0\\rangle \\rightarrow |x, x\\rangle$. Since\n",
    "\n",
    "$$\n",
    "ax = ax_{n-1} 2^{n-1} + \\cdots + a x_1 2^1 + a x_0 2^0 = \\sum_{x_k} a 2^k\n",
    "$$\n",
    "\n",
    "we can combine modular adder to make a multiplier. The structure of a multiplier is shown in `Fig.3` . Each `Modadd` assigns $a2^i mod N$ as input with Toffoli gate. e.g. $7x mod 15$, where $a=7$，$7\\times 2^0 mod 15 = 7, 7\\times 2^1 mod 15 = 14$, then the input of first `Modadd` is 7 (0111). $n$ bits multiplier needs $6n+3$ qubits in total. The input is assigned to $regx_0\\sim regx_3$, modulo is assigned to $modulusN_0 \\sim modulusN_3$ and output located at $b_0\\sim b_4$. In `Fig.10` , the input is $x=3$, modulo $N=15$.\n",
    "\n",
    "`Fig.10` shows the circuit to compute $7 x\\mod 15$ where $x=3$. It may cost 20 seconds with a hardware of 8U+32G.\n",
    "\n",
    "<img src=\"images/Fig3_moduler_multiplier.jpg\" width=600>\n",
    "\n",
    "<img src=\"images/Fig10_7xmod15.jpg\" width=600>\n",
    "\n",
    "The code of modular multiplier and verification is as following."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "c52790ba-df85-4a5d-9acc-cc2c14260a47",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Verify the modular multiplier (about 20 seconds for 8U+32G computer):\n",
      "ket string: 1¦00000000000011000010011⟩\n",
      "q_mul = 3, c_mul = 3\n",
      "\n"
     ]
    }
   ],
   "source": [
    "def ModMulti7xmod15():\n",
    "    \"\"\"4-bit modular multiplier to compute 7x mod 15, from Fig.10\n",
    "    \"\"\"\n",
    "    ns = 5  # number of shift bit\n",
    "    cir = Circuit()\n",
    "    cir += UN(X, maps_obj=[5, 6, 7], maps_ctrl=[[0, 1], [0, 1], [0, 1]])\n",
    "    cir += shift(ModAdder(), ns)\n",
    "    cir += UN(X, maps_obj=[5, 6, 7], maps_ctrl=[[0, 1], [0, 1], [0, 1]])\n",
    "\n",
    "    cir += UN(X, maps_obj=[6, 7, 8], maps_ctrl=[[0, 2], [0, 2], [0, 2]])\n",
    "    cir += shift(ModAdder(), ns)\n",
    "    cir += UN(X, maps_obj=[6, 7, 8], maps_ctrl=[[0, 2], [0, 2], [0, 2]])\n",
    "\n",
    "    cir += UN(X, maps_obj=[5, 7, 8], maps_ctrl=[[0, 3], [0, 3], [0, 3]])\n",
    "    cir += shift(ModAdder(), ns)\n",
    "    cir += UN(X, maps_obj=[5, 7, 8], maps_ctrl=[[0, 3], [0, 3], [0, 3]])\n",
    "\n",
    "    cir += UN(X, maps_obj=[5, 6, 8], maps_ctrl=[[0, 4], [0, 4], [0, 4]])\n",
    "    cir += shift(ModAdder(), ns)\n",
    "    cir += UN(X, maps_obj=[5, 6, 8], maps_ctrl=[[0, 4], [0, 4], [0, 4]])\n",
    "\n",
    "    cir += X(0)\n",
    "    cir += UN(X, maps_obj=[9, 10, 11, 12],\n",
    "              maps_ctrl=[[0, 1], [0, 2], [0, 3], [0, 4]])\n",
    "    cir += X(0)\n",
    "    return cir\n",
    "\n",
    "\n",
    "def demo3():\n",
    "    \"\"\"Verify the modular multiplier\n",
    "    \"\"\"\n",
    "    print(\"Verify the modular multiplier (about 20 seconds for 8U+32G computer):\")\n",
    "    # calculate 7x mod n\n",
    "    ctrl = 1  # control bit\n",
    "    x = 9\n",
    "    n = 15\n",
    "    cir_ctrl = c2q([0], ctrl)\n",
    "    cir_x = c2q([4, 3, 2, 1], x)\n",
    "    cir_n = c2q([21, 20, 19, 18], n)\n",
    "    cir_7x = cir_ctrl + cir_x + cir_n + ModMulti7xmod15() + cir_n\n",
    "    # measure to get result\n",
    "    q_mul = q2c(cir_7x, [12, 11, 10, 9])\n",
    "    c_mul = (7 * x) % 15\n",
    "\n",
    "    print(f\"q_mul = {q_mul}, c_mul = {c_mul}\\n\")\n",
    "\n",
    "\n",
    "demo3()"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "9e59ed29-0158-4b72-adfa-e6d09af10a99",
   "metadata": {},
   "source": [
    "### Modular Exponentiation Circuit\n",
    "\n",
    "Modular Exponentiation Circuit maps $|x, 1, 0\\rangle = |x, a^x mod N, 0\\rangle$, some $|0\\rangle$ are auxiliary bits. Next we will see the theoretical part. Express $a$ and $x$ in binary mode:\n",
    "\n",
    "$$\n",
    "a = a_{n-1} 2^{n-1} +\\cdots + a_1 2 + a_0\n",
    "$$\n",
    "\n",
    "$$\n",
    "x = x_{n-1} 2^{n-1} +\\cdots + x_1 2 + x_0\n",
    "$$\n",
    "\n",
    "then\n",
    "\n",
    "$$\n",
    "a^x = a^{x_{n-1}2^{n-1}} \\times \\cdots\\times a^{x_1 2}\\times a^{x_0}\n",
    "$$\n",
    "\n",
    "To realize the circuit, VBE proposes a quantum circuit as illustrated in `Fig.4` . The circuit consists of a series of modular multiplier pair (in a pair, one is the corresponding inverse circuit) with swap gates in the middle of each pair to preserve each multiplication result. The inverse circuit is for uncomputation of multiplication operation, preparing the circuit for the multiplication of the next bit. When two integrals $a, b$ satisfy $ab\\equiv 1 mod N$, we can say $b$ is the inverse digit of $a$ for $N$, such as 13 is reverse digit of 7 for 15, since $7\\times 13 mod 15 = 1$. In $CMODMULT^{-1}$ block, we first get the circuit of reverse digit, then reverse the circuit.\n",
    "\n",
    "<img src=\"images/Fig4_modular_exp.jpg\" width=600>\n",
    "\n",
    "`Fig.12` is a 4-bit modular exponentiation circuit to compute $7^x mod 15$. The input lies in $regx_e xp_0 \\sim regx_e xp_3$ and the output in $regx_0 \\sim regx_3$. We can see $7^{2^0} mod 15 = 7^1 mod 15 = 7$，$7^{2^1} mod 15 = 4$，$7^{2^2} mod 15 = 1, 7^{2^3} mod 15 = 1$, and their inverses are $13, 4, 1, 1$ respectively, they are the values of multiplier in `Fig.12` .\n",
    "\n",
    "<img src=\"images/Fig12_modular_exp.jpg\" width=800>\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "e95fe6d5-eb72-49a0-9fb8-c2ba0938dc4e",
   "metadata": {},
   "source": [
    "Here we show the code of multipliers and their inverse multipliers used in `Fig.12` .\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "346c5ddb-e40e-4611-ab4d-cd112351d28d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def ModMulti4xmod15():\n",
    "    \"\"\"4-bit mudular multiplier for 4x mod 15.\n",
    "    \"\"\"\n",
    "    ns = 5  # number of shift\n",
    "    cir = Circuit()\n",
    "    cir += UN(X, maps_obj=[7], maps_ctrl=[[0, 1]])\n",
    "    cir += shift(ModAdder(), ns)\n",
    "    cir += UN(X, maps_obj=[7, 8], maps_ctrl=[[0, 1], [0, 2]])\n",
    "    cir += shift(ModAdder(), ns)\n",
    "    cir += UN(X, maps_obj=[8, 5], maps_ctrl=[[0, 2], [0, 3]])\n",
    "    cir += shift(ModAdder(), ns)\n",
    "    cir += UN(X, maps_obj=[5, 6], maps_ctrl=[[0, 3], [0, 4]])\n",
    "    cir += shift(ModAdder(), ns)\n",
    "    cir += UN(X, maps_obj=[6], maps_ctrl=[[0, 4]])\n",
    "    cir += X(0)\n",
    "    cir += UN(X, maps_obj=[9, 10, 11, 12],\n",
    "              maps_ctrl=[[0, 1], [0, 2], [0, 3], [0, 4]])\n",
    "    cir += X(0)\n",
    "    return cir\n",
    "\n",
    "\n",
    "def ModMulti1xmod15(ns=5):\n",
    "    \"\"\"4-bit mudular multiplier for 1x mod 15.\n",
    "    \"\"\"\n",
    "    ns = 5  # number of shift\n",
    "    cir = Circuit()\n",
    "    cir += UN(X, maps_obj=[5], maps_ctrl=[[0, 1]])\n",
    "    cir += shift(ModAdder(), ns)\n",
    "    cir += UN(X, maps_obj=[5, 6], maps_ctrl=[[0, 1], [0, 2]])\n",
    "    cir += shift(ModAdder(), ns)\n",
    "    cir += UN(X, maps_obj=[6, 7], maps_ctrl=[[0, 2], [0, 3]])\n",
    "    cir += shift(ModAdder(), ns)\n",
    "    cir += UN(X, maps_obj=[7, 8], maps_ctrl=[[0, 3], [0, 4]])\n",
    "    cir += shift(ModAdder(), ns)\n",
    "    cir += UN(X, maps_obj=[8], maps_ctrl=[[0, 4]])\n",
    "    cir += X(0)\n",
    "    cir += UN(X, maps_obj=[9, 10, 11, 12],\n",
    "              maps_ctrl=[[0, 1], [0, 2], [0, 3], [0, 4]])\n",
    "    cir += X(0)\n",
    "    return cir\n",
    "\n",
    "\n",
    "def ModMulti13xmod15():\n",
    "    \"\"\"4-bit mudular multiplier for 13x mod 15.\n",
    "    \"\"\"\n",
    "    ns = 5  # number of shift\n",
    "    cir = Circuit()\n",
    "    cir += UN(X, maps_obj=[5, 7, 8], maps_ctrl=[[0, 1], [0, 1], [0, 1]])\n",
    "    cir += shift(ModAdder(), ns)\n",
    "    cir += UN(X, maps_obj=[5, 7, 8], maps_ctrl=[[0, 1], [0, 1], [0, 1]])\n",
    "\n",
    "    cir += UN(X, maps_obj=[5, 6, 8], maps_ctrl=[[0, 2], [0, 2], [0, 2]])\n",
    "    cir += shift(ModAdder(), ns)\n",
    "    cir += UN(X, maps_obj=[5, 6, 8], maps_ctrl=[[0, 2], [0, 2], [0, 2]])\n",
    "\n",
    "    cir += UN(X, maps_obj=[5, 6, 7], maps_ctrl=[[0, 3], [0, 3], [0, 3]])\n",
    "    cir += shift(ModAdder(), ns)\n",
    "    cir += UN(X, maps_obj=[5, 6, 7], maps_ctrl=[[0, 3], [0, 3], [0, 3]])\n",
    "\n",
    "    cir += UN(X, maps_obj=[6, 7, 8], maps_ctrl=[[0, 4], [0, 4], [0, 4]])\n",
    "    cir += shift(ModAdder(), ns)\n",
    "    cir += UN(X, maps_obj=[6, 7, 8], maps_ctrl=[[0, 4], [0, 4], [0, 4]])\n",
    "\n",
    "    cir += UN(X, maps_obj=[8], maps_ctrl=[[0, 4]])\n",
    "    cir += X(0)\n",
    "    cir += UN(X, maps_obj=[9, 10, 11, 12],\n",
    "              maps_ctrl=[[0, 1], [0, 2], [0, 3], [0, 4]])\n",
    "    cir += X(0)\n",
    "    return cir\n",
    "\n",
    "\n",
    "def ModMulti4xmod15Rev():\n",
    "    \"\"\"Reversed 4-bit mudular multiplier for 4x mod 15.\n",
    "    \"\"\"\n",
    "    cir = ModMulti4xmod15()\n",
    "    cir.reverse()\n",
    "    return cir\n",
    "\n",
    "\n",
    "def ModMulti1xmod15Rev():\n",
    "    \"\"\"Reversed 4-bit mudular multiplier for 1x mod 15.\n",
    "    \"\"\"\n",
    "    cir = ModMulti1xmod15()\n",
    "    cir.reverse()\n",
    "    return cir\n",
    "\n",
    "\n",
    "def ModMulti13xmod15Rev():\n",
    "    \"\"\"Reversed 4-bit mudular multiplier for 13x mod 15.\n",
    "    \"\"\"\n",
    "    cir = ModMulti13xmod15()\n",
    "    cir.reverse()\n",
    "    return cir"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "8935b9af-3d6b-4888-aa89-a921e444b71f",
   "metadata": {},
   "source": [
    "At last we give the code of modular exponentiation circuit in `Fig.12` which calculate $7^a mod 15$, then check the result with $a=3$.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8ddbd59a-c7f2-4466-9cf0-1913437fffe7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def ModExp():\n",
    "    \"\"\"4-bit modular exponentiation circuit, from Fig.12\n",
    "    \"\"\"\n",
    "    ns = 4\n",
    "    cir = Circuit()\n",
    "    cir += X(4, 0)\n",
    "    cir += X(5)\n",
    "    cir += shift(ModMulti7xmod15(), ns)\n",
    "    cir += UN(SWAP, maps_obj=[(5, 13), (6, 14), (7, 15), (8, 16)])\n",
    "    cir += shift(ModMulti13xmod15Rev(), ns)\n",
    "\n",
    "    cir += UN(X, maps_obj=[4, 4], maps_ctrl=[0, 1])\n",
    "    cir += shift(ModMulti4xmod15(), ns)\n",
    "    cir += UN(SWAP, maps_obj=[(5, 13), (6, 14), (7, 15), (8, 16)])\n",
    "    cir += shift(ModMulti4xmod15Rev(), ns)\n",
    "\n",
    "    cir += UN(X, maps_obj=[4, 4], maps_ctrl=[1, 2])\n",
    "    cir += shift(ModMulti1xmod15(), ns)\n",
    "    cir += UN(SWAP, maps_obj=[(5, 13), (6, 14), (7, 15), (8, 16)])\n",
    "    cir += shift(ModMulti1xmod15Rev(), ns)\n",
    "\n",
    "    cir += UN(X, maps_obj=[4, 4], maps_ctrl=[2, 3])\n",
    "    cir += shift(ModMulti1xmod15(), ns)\n",
    "    cir += UN(SWAP, maps_obj=[(5, 13), (6, 14), (7, 15), (8, 16)])\n",
    "    cir += shift(ModMulti1xmod15Rev(), ns)\n",
    "\n",
    "    cir += X(4, 3)\n",
    "    return cir\n",
    "\n",
    "\n",
    "def demo4():\n",
    "    \"\"\"Verify modular exponentiation circuit.\n",
    "    \"\"\"\n",
    "    # calculate 7^a mod n\n",
    "    print(\"Verify modular exponentiation circuit (about 20 minutes\\\n",
    "              for 8U+32G computer):\")\n",
    "    a = 3\n",
    "    n = 15\n",
    "    cir_a = c2q([3, 2, 1, 0], a)\n",
    "    cir_n = c2q([25, 24, 23, 22], n)\n",
    "    cir_expmod = cir_a + cir_n + ModExp() + cir_n\n",
    "\n",
    "    q_res = q2c(cir_expmod, [8, 7, 6, 5])\n",
    "    c_res = (7**a) % n\n",
    "\n",
    "    print(f\"q_res = {q_res}, c_res = {c_res}\\n\")\n",
    "\n",
    "\n",
    "demo4()"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "94fb02d9-c47f-4045-9424-6ea5a9b6db66",
   "metadata": {},
   "source": [
    "Output：\n",
    "\n",
    "```text\n",
    "Verify modular exponentiation circuit (about 20 minutes for 8U+32G computer):\n",
    "ket string: 1¦000000000000000000110100011⟩\n",
    "q_res = 13, c_res = 13\n",
    "```\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "a8bdf0be-529e-45a3-96ce-fa1c94741095",
   "metadata": {},
   "source": [
    "## Future Work\n",
    "\n",
    "The circuits provided in this tutorial is the baseline implementation without considering optimization. A more recent literatures have proposed various techniques to be more efficient, such as utilizing the semi-classical Fourier Transform (qubit recycling), various tinkering to the modular exponentiation circuit to reduce circuit depth and width, or utilizing a whole new approach using QFT-based circuit for performing exponentiation.\n",
    "\n",
    "## Reference\n",
    "\n",
    "[H. T. Larasati and H. Kim, \"Simulation of Modular Exponentiation Circuit for Shor's Algorithm in Qiskit, 2020](https://ieeexplore.ieee.org/document/9310794)\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "mindspore",
   "language": "python",
   "name": "mindspore"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.6 (tags/v3.8.6:db45529, Sep 23 2020, 15:52:53) [MSC v.1927 64 bit (AMD64)]"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
